∞

好好学习，天天向上

Checkio.org | Mono Captcha题解

发表于 更新于 分类于 Disqus：
chekcio.org上的题目Mono Captcha解题思路及代码

昨天在checkio上做了一道挺有意思的题。这道题中同时用上了列表推导、filter、int、join、map、bin和数字异或的特性。将解题思路记下来，也算是对自己近期学习Python的一个总结吧~~

题目(译)

原题地址：Mono Captcha 让我们来教教机器人Stephan识别简单的数字。机器人使用低分辨率的等宽字体。你可以看看下面图片中的字体感受一下。这个字体具备一个像素错误的抗噪能力。 你的程序应该能够读取以二进制数字矩阵图像显示的数字。每一个数字最多只允许包含一个错误的像素。每个数字之间是一个像素的空间（例如"1"虽然比其他数字窄，但是还是具有3个像素的宽度）。

输入

一个图片，该图片用拥有取值为1或0的列表组成的列表 ## 输出 整型数字

例子

1
2
3
4
5
6
7
8
9
10
checkio([[0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0],
         [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
         [0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
         [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],
         [0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0]]) == 394
checkio([[0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0],
         [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
         [0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
         [0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0],
         [0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0]]) == 394

前提条件

矩阵行数 == 5 5 ≤ 矩阵列数 < 30 ∀ x ∈ 矩阵 : x == 0 or x == 1 数字宽度 == 3 每一个数字至多包含一个像素错误。 数字间宽度 == 1

题解

由于每个数字的宽度和数字间的间隔是固定的，因此可以分割输入矩阵为一个一个的数字块，然后比较该数字块与哪一个数字块最接近即可。因此，思路梳理为：分割 -> 查找 -> 拼接

分割

由于只能使用Python自带模块，因此不能考虑使用例如第三方模块numpy来进行简单快速的矩阵操作进行矩阵分割。此时，可以使用列表推导代替。 另外，由于每个数字的宽度是3， 数字间宽度为1，因此，第i个数字为矩阵的第1+i4列到第3+i4列。 此时，可以写出类似下面的代码来分割： 

1
2
def slice(array, index=0):
	return [item[1+index*4:4+index*4] for item in array]
## 查找 首先，我们需要建立一个正确的数字二进制矩阵集。这样的话，就可以将分割出来的每一个数字与标准进行对比。只要找到一个数字n，与分割出来的数字i最多存在一个位的不同，那么说明i所表示的就是数字n。 这里使用二进制异或的概念来实现。由于每个矩阵都是由0或1组成的，那么很容易就可以将每个数字转换为一个15位的二进制字符串。将二进制字符串m与分割出来的数字所转换成的二进制字符串j进行异或运算得到结果z。当z为0或者z的二进制表示中只包含一个"1"时，表明这个m对应的数字就是我们要找的数字。 根据上面分析得到的正确的数字二进制矩阵集如下： 
1
2
3
digits = {0b010110010010010:'1',0b111001011100111:'2',0b111001010001111:'3',
		0b101101111001001:'4',0b111100110001110:'5',0b011100111101011:'6',
		0b111001010100100:'7',0b111101111101111:'8',0b011101111001110:'9',0b110101101101011:'0'}
需要修改一下分割函数，使得返回的也是编码后的数字： 
1
2
def transfer(array, index=0):
	return int("".join(["".join(map(lambda i:str(i),item[1+index*4:4+index*4])) for item in array]),2)
对应的判断函数如下： 
1
func = lambda value, real=transfer(array,i): 1 == bin(value^real).count("1") or '0b0' == bin(value^real)
## 拼接 怎么根据查找到的二进制字符串找到对应的数字呢？此时我们可以用filter函数：filter(func,digits) 由于digits是字典，因此实际上func中的value取的是digits的键，这就是为什么digits长得这么怪异。另外，我们也可以利用digits的键值查找到对应的数字。 
1
digits[filter(func,digits)[0]]
# 完整代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def transfer(array, index=0):
	return int("".join(["".join(map(lambda i:str(i),item[1+index*4:4+index*4])) for item in array]),2)

def checkio(array):
	digits = {0b010110010010010:'1',0b111001011100111:'2',0b111001010001111:'3',
		0b101101111001001:'4',0b111100110001110:'5',0b011100111101011:'6',
		0b111001010100100:'7',0b111101111101111:'8',0b011101111001110:'9',0b110101101101011:'0'}
	
	res = ""
	#数字的个数可以用矩阵的列数len(array[0])/4得到，当然，python3k在这里需要修改一下
	for i in xrange(0,len(array[0])/4): 
		func = lambda value, real=transfer(array,i): 1 == bin(value^real).count("1") or '0b0' == bin(value^real)
		res+=digits[filter(func,digits)[0]]
	return int(res)

请言小午吃个甜筒~~